---
title: STL 容器
---

C++ 标准模板库 (STL) 提供了一组丰富的通用类和函数，它们实现了常见的数据结构和算法。**容器**是存储数据的对象。它们是模板类，这意味着它们可以容纳任何数据类型的元素。理解 STL 容器对于高效且稳健的 C++ 编程至关重要，它提供了 JavaScript 内置数组和对象类型的一个强大替代方案。

## 序列容器：`vector`、`list`、`deque`

序列容器以线性方式存储元素，允许通过其位置访问元素。

### `std::vector`

*   **动态数组：** 类似于 JavaScript 数组，`std::vector` 是一个动态数组，其大小可以增长或缩小。
*   **连续内存：** 元素存储在连续的内存位置，允许高效的随机访问 (O(1))。
*   **高效的尾部插入/删除：** 在尾部添加/移除元素是高效的 (摊销 O(1))。
*   **低效的中间插入/删除：** 在中间插入/删除需要移动元素 (O(n))。

<UniversalEditor title="Vector vs. JavaScript Array" compare={true}>
```javascript !! js
// JavaScript: 数组
let numbers = [1, 2, 3];
numbers.push(4); // 添加到尾部
console.log(numbers); // [1, 2, 3, 4]
console.log(numbers[1]); // 2 (随机访问)
numbers.splice(1, 0, 99); // 在中间插入
console.log(numbers); // [1, 99, 2, 3, 4]
```

```cpp !! cpp
// C++: std::vector
#include <iostream>
#include <vector>

int main() {
  std::vector<int> numbers = {1, 2, 3};
  numbers.push_back(4); // 添加到尾部
  // std::cout << "Vector: ";
  // for (int n : numbers) { std::cout << n << " "; }
  // std::cout << std::endl;

  // std::cout << "Element at index 1: " << numbers[1] << std::endl; // 2 (随机访问)

  numbers.insert(numbers.begin() + 1, 99); // 在中间插入
  // std::cout << "Vector after insert: ";
  // for (int n : numbers) { std::cout << n << " "; }
  // std::cout << std::endl;

  return 0;
}
```
</UniversalEditor>

### `std::list`

*   **双向链表：** 元素不连续存储。每个元素存储指向前一个和后一个元素的指针。
*   **高效的任意位置插入/删除：** 在列表中的任何位置添加/移除元素是高效的 (O(1))，一旦找到位置。
*   **低效的随机访问：** 通过索引访问元素需要遍历列表 (O(n))。

### `std::deque` (双端队列)

*   **块的动态数组：** 将元素存储在非连续的内存块中。
*   **高效的头部/尾部插入/删除：** 在两端添加/移除元素是高效的 (摊销 O(1))。
*   **高效的随机访问：** 支持随机访问 (O(1))，尽管比 `std::vector` 稍慢。

## 关联容器：`map`、`set`、`unordered_map`

关联容器以排序或哈希方式存储元素，允许根据键高效地查找。

### `std::map`

*   **排序的键值对：** 以键值对的形式存储元素，按键排序。
*   **唯一键：** 每个键必须是唯一的。
*   **对数时间复杂度：** 查找、插入和删除操作通常是 O(log n)，因为其底层是树状结构（通常是红黑树）。

<UniversalEditor title="Map vs. JavaScript Object" compare={true}>
```javascript !! js
// JavaScript: 对象 (用作哈希映射)
let userAges = {
  "Alice": 30,
  "Bob": 25
};
userAges["Charlie"] = 35; // 添加/更新
console.log(userAges["Alice"]); // 访问
console.log("Bob" in userAges); // 检查是否存在
delete userAges["Bob"]; // 删除
```

```cpp !! cpp
// C++: std::map
#include <iostream>
#include <map>
#include <string>

int main() {
  std::map<std::string, int> userAges;
  userAges["Alice"] = 30;
  userAges["Bob"] = 25;
  userAges["Charlie"] = 35; // 添加/更新

  // std::cout << "Alice's age: " << userAges["Alice"] << std::endl; // 访问

  // 检查是否存在
  // if (userAges.count("Bob")) {
  //   std::cout << "Bob exists." << std::endl;
  // }

  userAges.erase("Bob"); // 删除

  return 0;
}
```
</UniversalEditor>

### `std::set`

*   **排序的唯一元素：** 以排序顺序存储唯一元素。
*   **对数时间复杂度：** 查找、插入和删除是 O(log n)。

### `std::unordered_map`

*   **哈希的键值对：** 使用哈希表存储键值对。
*   **唯一键：** 每个键必须是唯一的。
*   **平均常数时间复杂度：** 查找、插入和删除通常平均为 O(1)，但在最坏情况下（哈希冲突）可能退化为 O(n)。

### `std::unordered_set`

*   **哈希的唯一元素：** 使用哈希表存储唯一元素。
*   **平均常数时间复杂度：** 查找、插入和删除通常平均为 O(1)。

## 容器适配器：`stack`、`queue`、`priority_queue`

容器适配器为底层容器提供受限接口，强制执行特定的数据访问模式。

### `std::stack`

*   **LIFO (后进先出)：** 元素从顶部添加和移除。
*   **操作：** `push`、`pop`、`top`、`empty`、`size`。

### `std::queue`

*   **FIFO (先进先出)：** 元素添加到尾部，从头部移除。
*   **操作：** `push`、`pop`、`front`、`back`、`empty`、`size`。

### `std::priority_queue`

*   **最高优先级优先：** 元素根据其优先级（默认为最大元素）检索。
*   **操作：** `push`、`pop`、`top`、`empty`、`size`。

## 迭代器概念和用法

**迭代器**是行为类似指针的对象，允许你遍历容器的元素。它们提供了一种通用的方式来访问元素，无论容器类型如何。

*   `begin()`：返回指向第一个元素的迭代器。
*   `end()`：返回指向最后一个元素**之后**的元素的迭代器（一个哨兵）。
*   `*iterator`：解引用迭代器以获取元素的值。
*   `++iterator`：将迭代器移动到下一个元素。

<UniversalEditor title="迭代器用法比较" compare={true}>
```javascript !! js
// JavaScript: 迭代使用 for...of 或 forEach
let fruits = ["apple", "banana", "cherry"];
for (let fruit of fruits) {
  console.log(fruit);
}

fruits.forEach(fruit => console.log(fruit));
```

```cpp !! cpp
// C++: 迭代器
#include <iostream>
#include <vector>
#include <string>

int main() {
  std::vector<std::string> fruits = {"apple", "banana", "cherry"};

  // 使用传统 for 循环的迭代器
  // for (std::vector<std::string>::iterator it = fruits.begin(); it != fruits.end(); ++it) {
  //   std::cout << *it << std::endl;
  // }

  // 使用基于范围的 for 循环 (C++11+)，它内部使用迭代器
  // for (const std::string& fruit : fruits) {
  //   std::cout << fruit << std::endl;
  // }

  return 0;
}
```
</UniversalEditor>

## 容器性能特性分析

选择正确的容器对于性能至关重要。以下是常见操作的典型时间复杂度摘要：

| 容器         | 访问 (随机) | 插入 (任意位置) | 删除 (任意位置) | 搜索 (按值) |
| :---------------- | :-------------- | :------------------- | :------------------ | :---------------- |
| `std::vector`     | O(1)            | O(n)                 | O(n)                | O(n)              |
| `std::list`       | O(n)            | O(1)                 | O(1)                | O(n)              |
| `std::deque`      | O(1)            | O(n) (中间), O(1) (两端) | O(n) (中间), O(1) (两端) | O(n)              |
| `std::map`        | N/A             | O(log n)             | O(log n)            | O(log n)          |
| `std::set`        | N/A             | O(log n)             | O(log n)            | O(log n)          |
| `std::unordered_map` | N/A             | O(1) (平均), O(n) (最坏) | O(1) (平均), O(n) (最坏) | O(1) (平均), O(n) (最坏) |
| `std::unordered_set` | N/A             | O(1) (平均), O(n) (最坏) | O(1) (平均), O(n) (最坏) | O(1) (平均), O(n) (最坏) |

## 与 JavaScript 数组/对象的比较

JavaScript 的 `Array` 和 `Object` 类型功能非常强大，但它们抽象了底层的内存管理和特定的数据结构。C++ STL 容器提供了明确的选择，允许开发人员为其特定需求选择最高效的数据结构。

*   **JavaScript `Array`：** 对于数值索引，其行为有点像 `std::vector`，但也可以作为字符串键的哈希映射。它是一个单一、灵活的数据结构。
*   **JavaScript `Object`：** 主要是一个哈希映射（键值存储），功能类似 `std::unordered_map` 或 `std::map`，但没有 C++ 容器明确的性能保证或类型安全。

## 容器选择指南

*   **`std::vector`：** 序列的默认选择。当你需要快速随机访问和高效的尾部添加/删除时使用。避免频繁地在中间插入/删除。
*   **`std::list`：** 当你需要频繁地在序列中的任何位置插入/删除，并且随机访问不是主要考虑时使用。
*   **`std::deque`：** 当你需要高效地在两端插入/删除，并且也需要快速随机访问时使用。
*   **`std::map` / `std::set`：** 当你需要排序的键值对 (map) 或唯一的排序元素 (set) 以及操作的对数时间复杂度时使用。当顺序很重要时很有用。
*   **`std::unordered_map` / `std::unordered_set`：** 当你需要平均情况下 O(1) 的快速查找、插入和删除，并且元素顺序不重要时使用。哈希表类行为的理想选择。
*   **`std::stack` / `std::queue` / `std::priority_queue`：** 当你需要特定的 LIFO、FIFO 或基于优先级的访问模式时分别使用。

---

### 练习题：
1.  描述 `std::vector` 和 `std::list` 在其底层数据结构以及插入/删除和随机访问的性能特性方面的主要差异。
2.  何时会选择 `std::map` 而不是 `std::unordered_map`，反之亦然？解释其权衡。
3.  迭代器如何简化 C++ 中不同 STL 容器的使用？提供一个使用迭代器遍历 `std::vector` 和 `std::list` 的简单示例。

### 项目构想：
*   使用 `std::map` 实现一个简单的联系人管理系统，其中键是联系人的姓名（字符串），值是包含其电话号码和电子邮件的结构/类。允许用户添加、删除、搜索和显示联系人。然后，尝试使用 `std::vector` 的结构实现相同的系统，并比较搜索操作的复杂性。